/*
 * @Author: your name
 * @Date: 2024-06-21 09:53:58
 * @LastEditTime: 2024-06-21 10:01:37
 * @LastEditors: Please set LastEditors
 * @Description: In User Settings Edit
 * @FilePath: \.leetcode\343.整数拆分.cpp
 */
/*
 * @lc app=leetcode.cn id=343 lang=cpp
 *
 * [343] 整数拆分
 */

// @lc code=start
class Solution {
public:
    int integerBreak(int n) {
        vector<int> dp(n+1, 0);
        dp[1] = 1;
        dp[2] = 1;
        for(int i = 3; i <= n; i++){
            for(int j = 1; j <= i/2; j++){
                dp[i] = max(dp[i], max(j *(i-j), j *dp[i-j]));
            }
        }
        return dp[n];
    }
};
// @lc code=end
// dp[i]表示拆分第i个数字，得到的最大的乘积，然后递推公式里包含 拆与不拆的结果的判断
